Language/OS - Multiplatform Resource Library/LANGUAGE OS.iso/simula/books/books.lha/kirkerud/quicksort.sim

Text File | 1993-08-16 | 1KB | 30 lines

procedure Quicksort(table, low_bound, high_bound);
    integer array table;  integer low_bound, high_bound;
  !  Sorts the elements in table(low_bound : high_bound) in non-decreasing order;
if low_bound < high_bound then
begin integer some_value, last_below, last_equal,  first_above, ind, x;
  some_value  := table(low_bound);
  last_below  := low_bound - 1;
  last_equal  := low_bound;
  first_above := high_bound + 1;
  ind         := low_bound + 1;
  while ind < first_above do
    begin
      x := table(ind);
      if x < some_value then
        begin
          last_below := last_below + 1;     last_equal := last_equal + 1;
          table(ind) := table(last_below);  table(last_below) := x;
          ind := ind + 1;
        end else
      if x = some_value then
        begin last_equal := last_equal + 1;  ind := ind + 1 end
      else begin
          first_above := first_above - 1;
          table(ind) := table(first_above);  table(first_above) := x;
        end;
    end;
  Quicksort(table,   low_bound, last_below);
  Quicksort(table, first_above, high_bound);
end of Quicksort;